package main.Q301_400;

import java.util.*;

public class Q371_380 {
    public static void main(String[] args) {
        System.out.println("Question371：两整数之和");
        System.out.println("Question372：");
        System.out.println("Question373：查找和最小的K对数字");
        System.out.println("Question374：猜数字大小");
        System.out.println("Question375：");
        System.out.println("Question376：摆动序列");
        System.out.println("Question377：组合总和Ⅳ");
        System.out.println("Question378：有序矩阵中第K小的元素");
        System.out.println("Question379：");
        System.out.println("Question380：O(1) 时间插入、删除和获取随机元素");
    }
}

class Question371{
    public static int getSum(int a, int b) {
        int result=0,temp=0;//不要位移结果，记录每个位的状态并位移至指定位置
        for (int i=0;i<32;i++){
            if ((a>>i&1)==1&&(b>>i&1)==1){//末尾均为1
                result|=(temp<<i);
                temp=1;//进位标志
            }else if ((a>>i&1)==1||(b>>i&1)==1){//末位只有一个1
                result|=((1^temp)<<i);
            }else {//末位均为0
                result|=(temp<<i);//是否进位
                temp=0;
            }
        }
        return result;
    }
}

class Question373{
    public class Element{
        public int u;
        public int v;
        public Element(int u,int v){
            this.u=u;
            this.v=v;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> list=new ArrayList<>();
        Element[] elements=new Element[nums1.length* nums2.length];
        int index=0;
        for (int i=0;i< nums1.length;i++){
            for (int j=0;j< nums2.length;j++){
                Element temp=new Element(nums1[i],nums2[j]);
                elements[index]=temp;
                index++;
            }
        }
        Arrays.sort(elements, new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return (o1.u+ o1.v)-(o2.u+ o2.v);
            }
        });
        for (int i=0;i<k;i++){
            if (i< elements.length) {
                List<Integer> tempList = new ArrayList<>();
                tempList.add(elements[i].u);
                tempList.add(elements[i].v);
                list.add(tempList);
            }
        }
        return list;
    }
}

class Question374{
    public int guessNumber(int n) {
        int left = 1, right = n,result=0;
        while (left<=right){
//            int mid=left+(right-left)/2;
//            if (guess(mid)>0) left=mid+1;
//            else if (guess(mid)<0) right=mid-1;
//            else {
//                result=mid;
//                break;
//            }
        }
        return result;
    }
}

class Question376{
    public int wiggleMaxLength(int[] nums) {
        int length= nums.length;
        if (length<2) return length;
        int prev=nums[1]-nums[0];
        int ret= prev!=0 ? 2 : 1;
        for (int i=2;i<length;i++){
            int diff=nums[i]-nums[i-1];
            if ((diff>0&&prev<=0)||(diff<0&&prev>=0)) {
                ret++;
                prev=diff;
            }
        }
        return ret;
    }
}

class Question377{
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for (int i=1;i< dp.length;i++){
            int count=0;
            for (int j=0;j< nums.length;j++){
                count+= i-nums[j]>=0? dp[i-nums[j]] : 0;
            }
            dp[i]=count;
        }
        return dp[target];
    }
}

class Question378{
    public static int kthSmallest(int[][] matrix, int k) {
        int[] sortArr=new int[matrix.length*matrix.length];
        int index=0;
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix.length;j++){
                sortArr[index++]=matrix[i][j];
            }
        }
        Arrays.sort(sortArr);
        return sortArr[k-1];
    }
}

class Question380{
    private List<Integer> list;
    private int size;
    private Random random;
    public Question380() {
        this.list=new ArrayList<>();
        this.size=0;
        this.random=new Random();
    }

    public boolean insert(int val) {
        if (list.contains(val)) return false;
        else {
            list.add(val);
            size++;
            return true;
        }
    }

    public boolean remove(int val) {
        if (list.contains(val)) {
            list.remove(new Integer(val));
            size--;
            return true;
        }else return false;
    }

    public int getRandom() {
        int index=0+random.nextInt(size);
        return list.get(index);
    }
}